# Problem 18
#
# By starting at the top of the triangle below and moving to adjacent
# numbers on the row below, the maximum total from top to bottom is 23.
#
#                  3
#                 7 4
#                2 4 6
#               8 5 9 3
#
# That is, 3 + 7 + 4 + 9 = 23.
# 
# Find the maximum total from top to bottom of the triangle below:
# (see code)
#
# NOTE: As there are only 16384 routes, it is possible to solve this 
# problem by trying every route. However, Problem 67, is the same challenge
# with a triangle containing one-hundred rows; it cannot be solved by brute
# force, and requires a clever method! ;o)

t = [
#[int(e) for e in "3".split()],
#[int(e) for e in "7 4".split()],
#[int(e) for e in "2 4 6".split()],
#[int(e) for e in "8 5 9 3".split()]

[int(e) for e in "75".split()],
[int(e) for e in "95 64".split()],
[int(e) for e in "17 47 82".split()],
[int(e) for e in "18 35 87 10".split()],
[int(e) for e in "20 04 82 47 65".split()],
[int(e) for e in "19 01 23 75 03 34".split()],
[int(e) for e in "88 02 77 73 07 63 67".split()],
[int(e) for e in "99 65 04 28 06 16 70 92".split()],
[int(e) for e in "41 41 26 56 83 40 80 70 33".split()],
[int(e) for e in "41 48 72 33 47 32 37 16 94 29".split()],
[int(e) for e in "53 71 44 65 25 43 91 52 97 51 14".split()],
[int(e) for e in "70 11 33 28 77 73 17 78 39 68 17 57".split()],
[int(e) for e in "91 71 52 38 17 14 91 43 58 50 27 29 48".split()],
[int(e) for e in "63 66 04 68 89 53 67 30 73 16 69 87 40 31".split()],
[int(e) for e in "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23".split()]

]


#def best_path(ta, row, i):
#    arr = [ ta[row][i] ]
#    if row == len(ta)-2:
#        if ta[row+1][i] > ta[row+1][i+1]:
#            arr.append(ta[row+1][i])
#        else:
#            arr.append(ta[row+1][i+1])
#    else:
#        lbest = best_path(ta, row+1, i)
#        rbest = best_path(ta, row+1, i+1)
#        if sum(lbest) > sum(rbest):
#            arr.extend(lbest)     
#        else:
#            arr.extend(rbest)
#    return arr

def inverted_best_path(ta):
    penu = len(ta)-2
    for row in range(penu, -1, -1):
        tmp = []
        for i in range(0, len(ta[row])):
            if ta[row+1][i] > ta[row+1][i+1]:
                tmp.append(ta[row][i] + ta[row+1][i])
            else:
                tmp.append(ta[row][i] + ta[row+1][i+1])
        ta[row] = tmp
    return ta[0][0]

ans = inverted_best_path(t)
print "->", ans
